1. Process Id: A unique identifier assigned by the operating system
2. Process State: Can be ready, running, etc.
3. CPU registers: Like the Program Counter (CPU registers must be saved and
restored when a process is swapped in and out of CPU)
4. Accounts information: This includes the amount of CPU used for the process
execution, time limits, execution ID etc.
5. I/O status information: For example, devices allocated to the process,
open files, etc.
6. CPU scheduling information: For example, Priority (Different processes
may have different priorities, for example, a short process maybe
assigned a low priority in the shortest job first scheduling)
| Properties | DISPATCHER | SCHEDULER |
|---|---|---|
| Definition: | Dispatcher is a module that gives control of CPU to the process selected by short term scheduler | Scheduler is something which selects a process among various processes |
| Types: | There are no diifrent types in dispatcher.It is just a code segment. | There are 3 types of scheduler i.e. Long-term, Short-term, Medium-term |
| Dependency: | Working of dispatcher is dependednt on scheduler.Means dispatcher have to wait untill scheduler selects a process. | Scheduler works idependently.It works immediately when needed |
| Algorithm: | Dispatcher has no specific algorithm for its implementation | Scheduler works on various algorithm such as FCFS, SJF, RR etc. |
| Time Taken: | The time taken by dispatcher is called dispatch latency. | TIme taken by scheduler is usually negligible.Hence we neglect it. |
| Functions: | Dispatcher is also responsible for:Context Switching, Switch to user mode, Jumping to proper location when process again restarted | The only work of scheduler is selection of processes. |
Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turn Around Time - Burst Time
Response Ratio = (Waiting Time + Burst time) / Burst time
1- Input the processes along with their burst time (bt).
2- Find the waiting time (wt) for all processes.
3- As the first process that comes need not to wait so
waiting time for process 1 will be 0 i.e. wt[0] = 0.
4- Find waiting time for all other processes i.e. for
process i ->
wt[i] = bt[i-1] + wt[i-1] .
5- Find turnaround time = waiting_time + burst_time
for all processes.
6- Find average waiting time =
total_waiting_time / no_of_processes.
7- Similarly, find average turnaround time =
total_turn_around_time / no_of_processes.
1- Sort all the processes in increasing order
according to burst time.
2- Then simply, apply FCFS.
1- Traverse until all process gets completely executed.
a) Find process with minimum remaining time at every single time lap.
b) Reduce its time by 1.
c) Check if its remaining time becomes 0.
d) Increment the counter of process completion.
e) Completion time of current process = current_time +1;
f) Calculate the waiting time for each completed process.
wt[i]= Completion time - arrival_time-burst_time
g) Increment time lap by one.
2- Find turnaround time (waiting_time+burst_time).
Let's look at the below problem.
| Process | Duration | Order | Arrival Time |
|---|---|---|---|
| P1 | 9 | 1 | 0 |
| P2 | 2 | 2 | 2 |
P1 waiting time: 4-2 = 2
P2 waiting time: 0
The average waiting time(AWT): (0 + 2) / 2 = 1
1) Sort the processes in increasing order of their arrival time.As an example, consider the following 4 processes (P1, P2, P3, P4):
2) Choose the process having the least arrival-time but the most burst-time.
Execute it for 1 unit/quantum.
Check if any other process arrives upto that point of execution.
3) Repeat above steps until all processes have been executed.
Process Arrival time Burst TimeExecution:
P1 1 ms 2 ms
P2 2 ms 4 ms
P3 3 ms 6 ms
P4 4 ms 8 ms
Total Turn Around Time = 68 ms
So, Average Turn Around Time = 68/4 = 17.00 ms
And, Total Waiting Time = 48 ms
So Average Waiting Time = 48/4 = 12.00 ms
1- First input the processes with their burst time
and priority.
2- Sort the processes, burst time and priority
according to the priority.
3- Now simply apply FCFS algorithm.
1) Create an array rem_bt[] to keep track of remainingOnce we have waiting times, we can compute turn around time tat[i] of a process as sum of waiting and burst times, i.e., wt[i] + bt[i]
burst time of processes. This array is initially a
copy of bt[] (burst times array)
2) Create another array wt[] to store waiting times
of processes. Initialize this array as 0.
3) Initialize time : t = 0
4) Keep traversing all processes while all processes
are not done. Do following for the ith process if it is not done yet.
a- If rem_bt[i] > quantum
(i) t = t + quantum
(ii) bt_rem[i] -= quantum;
c- Else // Last cycle for this process
(i) t = t + bt_rem[i];
(ii) wt[i] = t - bt[i]
(ii) bt_rem[i] = 0; // This process is over
- In this, Work = [0, 0, 0] &
Finish = [false, false, false, false, false]
- i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].
- Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &
Finish = [true, false, false, false, false].
- i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1, 0].
- Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &
Finish = [true, false, true, false, false].
- i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1, 3].
- Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] &
Finish = [true, true, true, false, false].
- i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1, 3].
- Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] &
Finish = [true, true, true, true, false].
- i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2, 4].
- Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] &
Finish = [true, true, true, true, true].
- Since Finish is a vector of all true it means there is no deadlock in this example.
ftok(): is use to generate a unique key.Interprocess Communication (IPC) is a mechanism that allows processes to communicate with each other and synchronize their actions. The communication between these processes can be seen as a method of co-operation between them. Processes can communicate with each other using these two ways:
shmget(): int shmget(key_t,size_tsize,intshmflg); upon successful completion,
shmget() returns an identifier for the shared memory segment.
shmat(): Before you can use a shared memory segment, you have to attach yourself to it using shmat(). void *shmat(int shmid ,void *shmaddr ,int shmflg);
shmid is a shared memory id. shmaddr specifies a specific address to use but we should set
it to zero and OS will automatically choose the address.
shmdt(): When you’re done with the shared memory segment, your program should
detach itself from it using shmdt(). int shmdt(void *shmaddr);
shmctl(): when you detach from shared memory,it is not destroyed. So, to destroy
shmctl() is used. shmctl(int shmid,IPC_RMID,NULL);
ftok(): is use to generate a unique key.
msgget(): either returns the message queue identifier for a newly created message
queue or returns the identifiers for a queue that exists with the same key value.
msgsnd(): Data is placed on to a message queue by calling msgsnd().
msgrcv(): messages are retrieved from a queue.
msgctl(): It performs various operations on a queue. Generally it is use to
destroy message queue.
// Complete Code
// Binary Semaphore containing
// a boolean value and queue q
// to keep track of processes
// entering critical section
struct BinSem
{
bool val;
Queue q;
};
// Global initialization
BinSem s(true, empty);
// wait() is called before critical section
// during entry
void wait()
{
// Checking if critical section is
// available or not
if (s.val == 1)
// acquiring the critical section
s.val = 0;
// if not available
else
{
1. Put this process P in q;
2. sleep(P);
}
}
// signal() is called after critical section
// during exit
void signal
{
if (q is empty)
s.val = 1;
else
{
1. Pick a process P from q;
2. Wakeup(P);
}
}
Wait.let say we have 2 condition variables
signal.
If (x block queue empty)
// Ignore signal
else
// Resume a process from block queue.
Number of bits for frame = Size of physical memory/frame size
- To find the frame number.
- To go to the address specified by frame number.
= ( 1 - p ) * ( 300 ) + p * 9000000
= 300 + 8,999,700 * p
Many to many models.
Many to one model.
one to one model.
From Parent Process: Global Var = 0, Local Var = 0As can be seen, everything (global, local segment etc.) was duplicated in both child and parent. Only the variables corresponding to the child were incremented.
From Child Process: Global Var = 1, Local Var = 1
Inside Parent ProcessNOTE: Since, we loaded "ls" program into our child process, we never saw "Unreachable Code ..." string getting printed.
Still Executing Same Code
bin dev home lib lost+found mnt proc run srv tmp var
boot etc initrd.img lib64 media opt root sbin sys usr vmlinuz
Process ID: 10013
Start: 1557231700As we can see there is a difference of 5 secs. (because Child process was sleeping for 5secs). The parent waited for the child to exit.
End: 1557231705
1. Process Id: A unique identifier assigned by the operating system
2. Process State: Can be ready, running, etc.
3. CPU registers: Like the Program Counter (CPU registers must be saved and
restored when a process is swapped in and out of CPU)
4. Accounts information: This includes the amount of CPU used for the process
execution, time limits, execution ID etc.
5. I/O status information: For example, devices allocated to the process,
open files, etc.
6. CPU scheduling information: For example, Priority (Different processes
may have different priorities, for example, a short process maybe
assigned a low priority in the shortest job first scheduling)
| Properties | DISPATCHER | SCHEDULER |
|---|---|---|
| Definition: | Dispatcher is a module that gives control of CPU to the process selected by short term scheduler | Scheduler is something which selects a process among various processes |
| Types: | There are no diifrent types in dispatcher.It is just a code segment. | There are 3 types of scheduler i.e. Long-term, Short-term, Medium-term |
| Dependency: | Working of dispatcher is dependednt on scheduler.Means dispatcher have to wait untill scheduler selects a process. | Scheduler works idependently.It works immediately when needed |
| Algorithm: | Dispatcher has no specific algorithm for its implementation | Scheduler works on various algorithm such as FCFS, SJF, RR etc. |
| Time Taken: | The time taken by dispatcher is called dispatch latency. | TIme taken by scheduler is usually negligible.Hence we neglect it. |
| Functions: | Dispatcher is also responsible for:Context Switching, Switch to user mode, Jumping to proper location when process again restarted | The only work of scheduler is selection of processes. |
Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turn Around Time - Burst Time
Response Ratio = (Waiting Time + Burst time) / Burst time
1- Input the processes along with their burst time (bt).
2- Find the waiting time (wt) for all processes.
3- As the first process that comes need not to wait so
waiting time for process 1 will be 0 i.e. wt[0] = 0.
4- Find waiting time for all other processes i.e. for
process i ->
wt[i] = bt[i-1] + wt[i-1] .
5- Find turnaround time = waiting_time + burst_time
for all processes.
6- Find average waiting time =
total_waiting_time / no_of_processes.
7- Similarly, find average turnaround time =
total_turn_around_time / no_of_processes.
1- Sort all the processes in increasing order
according to burst time.
2- Then simply, apply FCFS.
1- Traverse until all process gets completely executed.
a) Find process with minimum remaining time at every single time lap.
b) Reduce its time by 1.
c) Check if its remaining time becomes 0.
d) Increment the counter of process completion.
e) Completion time of current process = current_time +1;
f) Calculate the waiting time for each completed process.
wt[i]= Completion time - arrival_time-burst_time
g) Increment time lap by one.
2- Find turnaround time (waiting_time+burst_time).
Let's look at the below problem.
| Process | Duration | Order | Arrival Time |
|---|---|---|---|
| P1 | 9 | 1 | 0 |
| P2 | 2 | 2 | 2 |
P1 waiting time: 4-2 = 2
P2 waiting time: 0
The average waiting time(AWT): (0 + 2) / 2 = 1
1) Sort the processes in increasing order of their arrival time.As an example, consider the following 4 processes (P1, P2, P3, P4):
2) Choose the process having the least arrival-time but the most burst-time.
Execute it for 1 unit/quantum.
Check if any other process arrives upto that point of execution.
3) Repeat above steps until all processes have been executed.
Process Arrival time Burst TimeExecution:
P1 1 ms 2 ms
P2 2 ms 4 ms
P3 3 ms 6 ms
P4 4 ms 8 ms
Total Turn Around Time = 68 ms
So, Average Turn Around Time = 68/4 = 17.00 ms
And, Total Waiting Time = 48 ms
So Average Waiting Time = 48/4 = 12.00 ms
1- First input the processes with their burst time
and priority.
2- Sort the processes, burst time and priority
according to the priority.
3- Now simply apply FCFS algorithm.
1) Create an array rem_bt[] to keep track of remainingOnce we have waiting times, we can compute turn around time tat[i] of a process as sum of waiting and burst times, i.e., wt[i] + bt[i]
burst time of processes. This array is initially a
copy of bt[] (burst times array)
2) Create another array wt[] to store waiting times
of processes. Initialize this array as 0.
3) Initialize time : t = 0
4) Keep traversing all processes while all processes
are not done. Do following for the ith process if it is not done yet.
a- If rem_bt[i] > quantum
(i) t = t + quantum
(ii) bt_rem[i] -= quantum;
c- Else // Last cycle for this process
(i) t = t + bt_rem[i];
(ii) wt[i] = t - bt[i]
(ii) bt_rem[i] = 0; // This process is over
ftok(): is use to generate a unique key.Interprocess Communication (IPC) is a mechanism that allows processes to communicate with each other and synchronize their actions. The communication between these processes can be seen as a method of co-operation between them. Processes can communicate with each other using these two ways:
shmget(): int shmget(key_t,size_tsize,intshmflg); upon successful completion,
shmget() returns an identifier for the shared memory segment.
shmat(): Before you can use a shared memory segment, you have to attach yourself to it using shmat(). void *shmat(int shmid ,void *shmaddr ,int shmflg);
shmid is a shared memory id. shmaddr specifies a specific address to use but we should set
it to zero and OS will automatically choose the address.
shmdt(): When you’re done with the shared memory segment, your program should
detach itself from it using shmdt(). int shmdt(void *shmaddr);
shmctl(): when you detach from shared memory,it is not destroyed. So, to destroy
shmctl() is used. shmctl(int shmid,IPC_RMID,NULL);
ftok(): is use to generate a unique key.
msgget(): either returns the message queue identifier for a newly created message
queue or returns the identifiers for a queue that exists with the same key value.
msgsnd(): Data is placed on to a message queue by calling msgsnd().
msgrcv(): messages are retrieved from a queue.
msgctl(): It performs various operations on a queue. Generally it is use to
destroy message queue.
// Binary Semaphore containing
// a boolean value and queue q
// to keep track of processes
// entering critical section
struct BinSem
{
bool val;
Queue q;
};
// Global initialization
BinSem s(true, empty);
// wait() is called before critical section
// during entry
void wait()
{
// Checking if critical section is
// available or not
if (s.val == 1)
// acquiring the critical section
s.val = 0;
// if not available
else
{
1. Put this process P in q;
2. sleep(P);
}
}
// signal() is called after critical section
// during exit
void signal
{
if (q is empty)
s.val = 1;
else
{
1. Pick a process P from q;
2. Wakeup(P);
}
}
Wait.let say we have 2 condition variables
signal.
If (x block queue empty)
// Ignore signal
else
// Resume a process from block queue.
- In this, Work = [0, 0, 0] &
Finish = [false, false, false, false, false]
- i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].
- Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &
Finish = [true, false, false, false, false].
- i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1, 0].
- Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &
Finish = [true, false, true, false, false].
- i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1, 3].
- Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] &
Finish = [true, true, true, false, false].
- i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1, 3].
- Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] &
Finish = [true, true, true, true, false].
- i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2, 4].
- Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] &
Finish = [true, true, true, true, true].
- Since Finish is a vector of all true it means there is no deadlock in this example.
// CPP program to illustrate
// concept of Virtual Functions
#include <iostream>
using namespace std;
class base {
public:
virtual void print()
{
cout << "print base class" << endl;
}
void show()
{
cout << "show base class" << endl;
}
};
class derived : public base {
public:
void print()
{
cout << "print derived class" << endl;
}
void show()
{
cout << "show derived class" << endl;
}
};
int main()
{
base* bptr;
derived d;
bptr = &d;
// virtual function, binded at runtime
bptr->print();
// Non-virtual function, binded at compile time
bptr->show();
}print derived class
show base class
print in superclass.
print in subclass.
| S.NO | Process | Thread |
|---|---|---|
| 1. | Process means any program is in execution. | Thread means segment of a process. |
| 2. | Process takes more time to terminate. | Thread takes less time to terminate. |
| 3. | It takes more time for creation. | It takes less time for creation. |
| 4. | It also takes more time for context switching. | It takes less time for context switching. |
| 5. | Process is less efficient in term of communication. | Thread is more efficient in term of communication. |
| 6. | Process consume more resources. | Thread consume less resources. |
| 7. | Process is isolated. | Threads share memory. |
1- Input the processes along with their burst time (bt).
2- Find waiting time (wt) for all processes.
3- As first process that comes need not to wait so
waiting time for process 1 will be 0 i.e. wt[0] = 0.
4- Find waiting time for all other processes i.e. for
process i ->
wt[i] = bt[i-1] + wt[i-1] .
5- Find turnaround time = waiting_time + burst_time
for all processes.
6- Find average waiting time =
total_waiting_time / no_of_processes.
7- Similarly, find average turnaround time =
total_turn_around_time / no_of_processes.
P1 waiting time: 4-2 = 2
P2 waiting time: 0
The average waiting time(AWT): (0 + 2) / 2 = 1
1- Traverse until all process gets completely
executed.
a) Find process with minimum remaining time at
every single time lap.
b) Reduce its time by 1.
c) Check if its remaining time becomes 0
d) Increment the counter of process completion.
e) Completion time of current process =
current_time +1;
e) Calculate waiting time for each completed
process.
wt[i]= Completion time - arrival_time-burst_time
f)Increment time lap by one.
2- Find turnaround time (waiting_time+burst_time).
Process Arrival time Burst Time
P1 1 ms 2 ms
P2 2 ms 4 ms
P3 3 ms 6 ms
P4 4 ms 8 ms
Turn Around Time (TAT)
= (Complition Time) - (Arival Time)
Also, Waiting Time (WT)
= (Turn Around Time) - (Burst Time)
Total Turn Around Time = 68 ms
So, Average Turn Around Time = 68/4 = 17.00 ms
And, Total Waiting Time = 48 ms
So Average Waiting Time = 48/4 = 12.00 ms
1- First input the processes with their burst time
and priority.
2- Sort the processes, burst time and priority
according to the priority.
3- Now simply apply FCFS algorithm.
// Java implementation of a producer and consumer
// that use semaphores to control synchronization.
import java.util.concurrent.Semaphore;
class Q
{
// an item
int item;
// semCon initialized with 0 permits
// to ensure put() executes first
static Semaphore semCon = new Semaphore(0);
static Semaphore semProd = new Semaphore(1);
// to get an item from buffer
void get()
{
try {
// Before consumer can consume an item,
// it must acquire a permit from semCon
semCon.acquire();
}
catch(InterruptedException e) {
System.out.println("InterruptedException caught");
}
// consumer consuming an item
System.out.println("Consumer consumed item : " + item);
// After consumer consumes the item,
// it releases semProd to notify producer
semProd.release();
}
// To put an item in buffer
void put(int item)
{
try {
// Before producer can produce an item,
// it must acquire a permit from semProd
semProd.acquire();
} catch(InterruptedException e) {
System.out.println("InterruptedException caught");
}
// producer producing an item
this.item = item;
System.out.println("Producer produced item : " + item);
// After producer produces the item,
// it releases semCon to notify consumer
semCon.release();
}
}
// Producer class
class Producer implements Runnable
{
Q q;
Producer(Q q) {
this.q = q;
new Thread(this, "Producer").start();
}
public void run() {
for(int i=0; i < 5; i++)
// producer put items
q.put(i);
}
}
// Consumer class
class Consumer implements Runnable
{
Q q;
Consumer(Q q){
this.q = q;
new Thread(this, "Consumer").start();
}
public void run()
{
for(int i=0; i < 5; i++)
// consumer get items
q.get();
}
}
// Driver class
class PC
{
public static void main(String args[])
{
// creating buffer queue
Q q = new Q();
// starting consumer thread
new Consumer(q);
// starting producer thread
new Producer(q);
}
}Producer produced item : 0
Consumer consumed item : 0
Producer produced item : 1
Consumer consumed item : 1
Producer produced item : 2
Consumer consumed item : 2
Producer produced item : 3
Consumer consumed item : 3
Producer produced item : 4
Consumer consumed item : 4
1) Let Work and Finish be vectors of length 'm' and 'n' respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4....n
2) Find an i such that both
a) Finish[i] = false
b) Needi <= Work
if no such i exists goto step (4)
3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)
4) if Finish [i] = true for all i
then the system is in a safe state
1) If Requesti <= Needi Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim.
2) If Requesti <= Available
Goto step (3); otherwise, Pi must wait, since the resources are not available.
3) Have the system pretend to have allocated the requested resources to process Pi by modifying the state as
follows:
Available = Available - Requesti
Allocationi = Allocationi + Requesti Needi = Needi- Requesti
Exception in thread "main" java.lang.OutOfMemoryError: Java heap spaceUsually, this error is thrown when the Java Virtual Machine cannot allocate an object because it is out of memory, and no more memory could be made available by the garbage collector.
i = j modulo m
where
i=cache line number
j= main memory block number
m=number of lines in the cache
Number of bits for frame = Size of physical memory/frame size